(1) Field of the Invention
The invention relates to cache replacement schemes. More specifically, the invention relates to combined round robin cache replacement and cache line locking schemes.
(2) Background
Various schemes exist for defining what data is replaced when a new data set is loaded into a cache. One favored scheme in direct mapped caches is a least recently used (LRU) scheme. In an LRU scheme, as the name implies, the block of data that has been used least recently is replaced with any incoming data. Because of the locality of reference common to computer software execution and data usage, this has been found to be a fairly efficient cache replacement scheme. However, as set associativity increases, the complexity and overhead for an LRU scheme make such schemes less attractive due to increasing hardware requirements.
Additionally, in content addressable memory (CAM)-based caches without separate decoders, high set-associativity is achieved, and identifying where to write fill data becomes increasingly problematic. One possible solution that has been employed is a round robin replacement scheme in which a circular shift register loops through identifying the line to be loaded. This has the effect of throwing away the oldest information in the cache, but the replacement is completely independent of the frequency of use. Thus, it can result in a greater amount of cache thrashing.
Some prior solutions to prevent data from being kicked out of the cache prematurely was to allow way locking. These systems failed to provide much granularity. For example, in a two-way cache, half the cache would be locked, even if the block of data to be retained was relatively small. This often results in inefficient cache usage.
A first plurality of latches are daisy chained together, forming a register, with each latch associated with a particular cache line. Similarly, a second plurality of latches are daisy chained together with each latch associated with a cache line. The first register defines a fill order of cache lines and the second register defines a lock order for the cache lines.